package com.jiang.daily.Q2272;

import java.util.Arrays;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/03/16 22:36
 */
class Solution {

    // 超时
    // public int largestVariance(String s) {
    //     char[] arr = s.toCharArray();
    //     // 统计每个字符出现的次数
    //     Map<Character, Integer> map1 = new HashMap<>();
    //     // 统计出现该次数有多少个字符
    //     Map<Integer, Integer> map2 = new HashMap<>();

    //     int res = 0;
    //     for (int i = 1; i < arr.length; i++) {
    //         map1.clear();
    //         map2.clear();
    //         int max = 1;
    //         int min = 1;
    //         map1.put(arr[i], 1);
    //         map2.put(1, 1);
    //         for (int j = i - 1; j >= 0; j--) {
    //             if (map1.containsKey(arr[j])) {
    //                 // 修改map1和最大出现次数
    //                 int cnt1 = map1.get(arr[j]);
    //                 max = Math.max(max, cnt1 + 1);
    //                 map1.put(arr[j], cnt1 + 1);

    //                 // 修改map2和最小出现次数
    //                 int cnt2 = map2.get(cnt1);
    //                 if (cnt2 == 1 && min == cnt1) {
    //                     min = cnt1 + 1;
    //                 }

    //                 map2.put(cnt1, cnt2 - 1);
    //                 map2.put(cnt1 + 1, map2.getOrDefault(cnt1 + 1, 0) + 1);

    //             } else {
    //                 map1.put(arr[j], 1);
    //                 int cnt = map2.get(1);
    //                 if (cnt == 0) {
    //                     min = 1;
    //                     map2.put(1, 1);
    //                 } else {
    //                     map2.put(1, cnt + 1);
    //                 }
    //             }
    //             // 修改res
    //             res = Math.max(res, max - min);
    //         }
    //     }

    //     return res;
    // }

    public int largestVariance(String s) {
        char[] cs = s.toCharArray();
        int n = cs.length;

        int ans = 0;
        int[][] count = new int[26][26];
        int[][] countWithB = new int[26][26];

        for (int i = 0; i < 26; i++)
            Arrays.fill(countWithB[i], -n);

        for (char c:cs) {
            int a = c - 'a';

            for (int b = 0; b < 26; ++b) {
                if (b == a)
                    continue;

                ++count[a][b];
                ++countWithB[a][b];
                countWithB[b][a] = --count[b][a];
                count[b][a] = Math.max(count[b][a], 0);
                ans = Math.max(ans, Math.max(countWithB[a][b], countWithB[b][a]));
            }
        }

        return ans;
    }
}
